package com.leetcode.No1775;

import org.junit.Test;

/**
 * @program: Solution
 * @description: 通过最少操作次数使数组的和相等
 * @author: Wang Zhihua
 * @date: 2022-12-09
 */
public class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        // 让nums1 成为元素和少的，让nums2成为多的
        int lessSum = 0;
        int moreSum = 0;
        for (int num : nums1) {
            lessSum += num;
        }
        for (int num : nums2) {
            moreSum += num;
        }
        if (lessSum > moreSum) {
            lessSum = lessSum ^ moreSum;
            moreSum = lessSum ^ moreSum;
            lessSum = lessSum ^ moreSum;

            int[] tmpNums = nums1;
            nums1 = nums2;
            nums2 = tmpNums;
        }
        int gap = moreSum - lessSum;
        int lessLen = nums1.length;
        int moreLen = nums2.length;

        // 判断是否可以让两数组实现和相等
        if (lessLen * 6 < moreLen) {
            return -1;
        }

        int[] lessNumFreq = new int[7];
        int[] moreNumFreq = new int[7];
        for (int num : nums1) {
            ++lessNumFreq[num];
        }
        for (int num : nums2) {
            ++moreNumFreq[num];
        }

        int result = 0;
        for (int i = 1; i <= 5; ++i) {
            int tmpFreq = Math.min(gap / (6 - i), lessNumFreq[i]);
            tmpFreq += (gap % (6 - i) > 0 && tmpFreq < lessNumFreq[i]) ? 1 : 0;
            gap -= tmpFreq * (6 - i);
            result += tmpFreq;
            if (gap <= 0) {
                break;
            }

            tmpFreq = Math.min(gap / (6 - i), moreNumFreq[7 - i]);
            tmpFreq += (gap % (6 - i) > 0 && tmpFreq < moreNumFreq[7 - i]) ? 1 : 0;
            gap -= tmpFreq * (6 - i);
            result += tmpFreq;
            if (gap <= 0) {
                break;
            }
        }
        return result;
    }

    @Test
    public void test() {
        int[] nums1;
        int[] nums2;

//        nums1 = new int[]{1,2,3,4,5,6};
//        nums2 = new int[]{1,1,2,2,2,2};
//        System.out.println(minOperations(nums1, nums2));
//
//        nums1 = new int[]{1,1,1,1,1,1,1};
//        nums2 = new int[]{6};
//        System.out.println(minOperations(nums1, nums2));
//
//        nums1 = new int[]{6,6};
//        nums2 = new int[]{1};
//        System.out.println(minOperations(nums1, nums2));

//        nums1 = new int[]{3,3,2,4,2,6,2};
//        nums2 = new int[]{6,2,6,6,1,1,4,6,4,6,2,5,4,2,1};
//        System.out.println(minOperations(nums1, nums2));

        nums1 = new int[]{1,2,5,4,3,3,5,1,1,6,2,5,4,4,5,6,6,4,2,5,6,2,3,4,5,2,4,4,3,6,6,5,4,1,2,1,2,3,3,2,6,1,1,1,1,3,5,6,2,1,1,1,4,6,5};
        nums2 = new int[]{1,5,5,2,1,1,1,1,4,4,4,1,5,2,2,4,6,5,1,5,3,5,6,2,3,1,5,4,4,1,2,4,1,1,6,3,6,4,4,4,3,5,5,5,2,6,4,2,5,4,2,6,3,4,6,1,5,3,2,3,5,2,1,3,2,4,4,4,5,3,5,5,4,1,1,6,5,6,3,5,3,6,5,6,5,4,4,4,5,6,6,6,4,2,4,6,1,2,1,5,3,4,5,5,6,6,1,4,3,1,5,3,4,1,2,1,4,4,5,6,5,3,1,5,1,3,3,6,5,3,5,6,2,6,3,1,2,3,3,1,1,4,3,2,6,6,2,1,2,4,3,5,5,4,3,1,1,5,2,5,1,4,5,6,4,5,2,1,2,5,3,2,6,3,4,3,4,5,4,6,3,4,4,3,3,4,2,2,6,2,6,3,1,1,5,3,1,1,4,2,5,5,5,4,3,6,5,5,5,1,1,3,6,2,3,6,3,4,2,5,4,4,3,5,6,4,3,5,1,1,3,3,1,1,6,4,6,2,1,4,3,5,5};
        System.out.println(minOperations(nums1, nums2));
    }
}
